// Exploration in memoization of Fibonacci numbers

// To solve the second problem mentioned in this PDF: 
// http://192.168.1.1/~skapoor/2011/csi/papers/inoi2008-qpaper.pdf

// Here's how a simple recursive definition of Fibonacci looks
def fib(n: Int): Int = {
    if(n == 1) 1
    else if(n == 2) 2
    else fib(n-1) + fib(n-2)
    
}

test("Fibonacci test") {
    fib(1) should equal(1)
    fib(2) should equal(2)
    fib(5) should equal(8)
}

// Definition modified to increment the number of calls and 
// print that out
def fib2(n: Int): Int = {
    var fibCalls:Array[Int] = new Array[Int](n+1)

    def fib1(n: Int): Int = {
        fibCalls(n) += 1
        if(n == 1) return 1
        else if(n == 2) return 2
        else return (fib1(n-1) + fib1(n-2))
    }
    
    val fibN = fib1(n)
    fibCalls.foreach(println)
    return fibN
}

def fib3(n: Int): Int = {
    var fibCalls:Array[Int] = new Array[Int](n+1)
    var fibValues:Array[Int] = new Array[Int](n+1)

    def fib1(n: Int): Int = {
        fibCalls(n) += 1
        if(fibValues(n) == 0)
        {
            if(n == 1) fibValues(1) = 1
            else if(n == 2) fibValues(2) = 2
            else {
                fibValues(n) = fib1(n-1) + fib1(n-2)
            }
        }
        return fibValues(n)
    }
    
    val fibN = fib1(n)
    fibCalls.foreach(println)
    return fibN
}


println("Fib " + fib2(35))
println("Fib " + fib3(35))

